The use and the popularity of computer systems have steadily increased since around the middle of the twentieth century. While this trend has been fuelled by many different advances in computer system technology, some fundamental aspects of overall computer system value remain unchanged. Perhaps the most basic touchstone of computer system value has been, and continues to be, the speed at which decisions can be made and calculations can be performed.
While the computer system's processor is arguably the most important computer system component, the speed at which a computer system performs does not depend solely on that one system component. The speed of other computer system components, such as computer system memory, can also dramatically effect overall computer system performance. Another important component is the computer system's programs. When a computer system carries out its tasks, it does so at the direction of its programs. The programs are said to "execute" on the computer system's processor. Thus, program execution speed is also a key element of overall system performance.
Computer programs are constructed using one or more programming languages. Like words written in English, a programming language is used to write a series of statements that have particular meaning to the drafter (i.e., the programmer). The programmer writes programs that execute on the computer system's processor to perform a particular function or calculation. These programs are written in human readable form by the programmer and then transformed through the use of a compiler into a form that can be understood by the computer system's processor. A fundamental concept found in virtually every programming language is the ability to direct the computer system to take different actions based on one or more conditions. For example, a programmer creating a program that generates account balances may write some code that instructs the computer system to display negative account balances in red and positive account balances in black. The high-level code statement written to represent this idea may be something like: IF account balance &lt;$0, THEN display account balance in red, ELSE display account balance in black. When compiled, high-level statements such as this are broken down into substatements such that the single statement set forth above would ultimately be represented by several smaller statements. Essentially, then, the compilation process converts these high level statements into a stream of smaller, substatements. Decisions contained in the statement stream, like the account balance decision, take on the form of what are called branches. It is the branches that create the different paths of statements which allow the program to generate different results based on different conditions. When taken together the branches of a program are said to form a branching structure.
Sometimes the branches and other statements of the statement stream can be understood directly by the computer system's processor. Other times, though, one or more subsequent transformations may be required to further break down the statements into even smaller substatements that can be understood by the computer system's processor. While the need for this multiple transformation scheme is brought on by factors that are not important here, the individual transformations within the series of transformations do provide an opportunity to optimize the statement stream to make it execute faster on the processor. A special type of compiler, called an optimizing compiler, is used for this purpose. While there are any number of well-known optimization techniques used to make the statement stream execute more quickly, it should be understood that some optimizations are best performed early in the transformation process while others are best performed late in the transformation process. In general early optimizations can be performed without concern for the specific type of processor involved, while late optimizations tend to be specific to a particular type of processor.
With that being said, another technique, called profiling, is used to enhance the various optimization techniques. The basic idea behind profiling involves 1) gathering information during execution of a program and 2) using the gathered information in a subsequent recompile to better optimize the program. While profiling techniques themselves come in a variety of forms, the profiling technique at issue here is referreed to as instrumentation. Instrumentation is performed by a mechanism in the compiler that is called an instrumenting profiler. An instrumenting profiler operates by inserting special instructions into the program during compilation. These special instructions, called hooks or branch counters, are placed at key branch locations in the program. Then, when the program executes, these hooks are used to keep track of the frequency with which the different branch statements are executed. The frequencies are essentially a measure of how many times particular paths are taken through the program's statements. As mentioned, this information is then used during a subsequent recompile to optimize the speed at which the program executes.
The problem addressed within this patent pertains to the use of instrumenting profilers in situations that require multiple transformations of the computer program. As mentioned earlier, the existence of multiple transformations provides an opportunity for both early and late optimizations. However, the multiple transformations also create a problem relative to instrumenting profilers because each time the program is transformed in the compilation process a new branching structure may be created. The problem, then, is how to select a branching structure for instrumentation. Which one should be chosen? Choosing a branching structure from an early transformation does not allow for an understanding of all branches that are introduced in subsequent transformations, but choosing a branching structure that is created in a later transformation means that the gathered information will not be meaningful, and thus useful, for the high-level optimizations that occur as part of earlier transformations.
One solution to this problem is to perform the instrumentation/recompilation process several times by using the branching structures generated at each level of transformation. While this approach does result in good overall optimization of the program, it is takes a great deal of time and effort, making it impractical in today's commercial environment where overall "time to market" is of paramount concern. Another solution is to simply rearrange the program manually (i.e, guess) for one or more branching structures, but of course such an approach is a "hit or miss" proposition.
Thus, today's computer system designers must decide whether to bypass the performance gains offered by profiling or to use an inefficient or inaccurate process.